/**
 * 
 * @Project HRL Simulation
 * @Date 20.06.2011
 * @Author Aebi Pascal, Kocher Marc, Sriranjan George
 * @School BFH-TI Biel, Projekt 1
 *
 */

package utils;

import java.lang.management.ManagementFactory;
import java.lang.management.ThreadMXBean;
import java.text.*;
import java.util.Iterator;
import java.util.Random;

public class SkipList {
	

	class SLNode implements Locator {
		SkipList skipList = SkipList.this;
		Comparable key;
		Object element=null;
	    // neighbpours
		SLNode above;
		SLNode below;
		SLNode after;
		SLNode before;
		
		
		SLNode(SLNode before, SLNode after, 
						SLNode below, SLNode above, 
						Comparable key, 
						Object value){
			this.before=before;
			this.after=after;
			this.below=below;
			this.above=above;
			if (before != null) {
				before.after=this;
			}
			if (after != null) {
				after.before=this;
			}
			if (below != null) {
				below.above=this;
			}
			if (above != null) {
				above.below=this;
			}
			this.key=key;
			this.element=value;
		}

		public Comparable key(){
			return key;
		}
		public Object element(){
			return element;
		}

	}


	
	public boolean debug;
	private SLNode topLeft;
	private SLNode bottomLeft;
	private SLNode topRight;
	private SLNode bottomRight;
	Comparable maxKey,minKey;
	
	private int size; 
	private int nodeCnt;
	private int height;

	private double w; 
	Random rand=new Random(1235);

	public SkipList(Comparable minKey, Comparable maxKey, double w){
		// erstelle Skelett 
		if (minKey.compareTo(maxKey)>=0) throw new RuntimeException("min >= max not allowed");
		bottomLeft = new SLNode(null,null,null,null,minKey,null);
		topLeft = new SLNode(null,null,bottomLeft,null,minKey,null);
		bottomRight = new SLNode(bottomLeft,null,null,null,maxKey,null);
		topRight = new SLNode(topLeft,null,bottomRight,null,maxKey,null);
		this.maxKey = maxKey;
		this.minKey = minKey;
		height = 2;
		this.w=w;
	}
	
	public int getHeight(){
		return height;
	}
	
	public Locator  next(Locator loc){
		SLNode n = (SLNode)loc;
		if (n.skipList != this) throw new RuntimeException("the locator does not belong to this List!");
		return n.after;
	}
	
	public boolean  hasNext(Locator loc){
		SLNode n = (SLNode)loc;
		if (n.skipList != this) throw new RuntimeException("the locator does not belong to this List!");
		return n.after != bottomRight;
	}

	public Locator findClosestBefore(Comparable key){
		// returns the locator with the largest key smaller than 'key';
		SLNode nd = topLeft;
		while (nd.below != null){
			nd=nd.below;
			while (key.compareTo(nd.after.key) >= 0) {
				nd=nd.after;
			}
		}
		while (nd.key.equals(key)) nd = nd.before; 
		return nd;
	}
	
	
	public Locator findClosestAfter(Comparable key){
		// returns the locator with the smallest key larger than 'key';
		SLNode nd = topRight;
		while (nd.below != null){
			nd=nd.below;
			while (key.compareTo(nd.before.key) <= 0) {
				nd=nd.before;
			}
		}
		while (nd.key.equals(key)) nd = nd.after; 
		return nd;
	}

	
	public Locator findItem(Comparable key){
		// returns the locator with the largest key smaller than 'key';
		SLNode nd = topLeft;
		while (nd.below != null){
			nd=nd.below;
			while (key.compareTo(nd.after.key) >= 0) {
				nd=nd.after;
			}
		}
		Locator loc = nd;
		if (loc.key().compareTo(key)==0) return loc;
		else return null;
	}
	

	public Locator insertItem(Comparable key, Object value){
		SLNode p = (SLNode) findClosestBefore(key);
		SLNode q = new SLNode(p,p.after,null,null,key,value);
		while (rand.nextDouble()<w){
			nodeCnt++;
			// insert a additional link
			while (p.above == null){ // find next tower
				p=p.before;
			}
			p=p.above;  // go 1 step upwards 
			// are we at top?
			if (p==topLeft){
				//expand one level
				topLeft = new SLNode(null,null,p,null,topLeft.key,null);
				topRight = new SLNode(topLeft,null,topRight,null,topRight.key,null);
				height++;
			}
			// insert the additional node
			q= new SLNode(p,p.after,q,null,key,value);
		}
		size++;
		nodeCnt++;
		return q;
	}
	
	public void removeItem(Locator loc){
		if (loc==null) return;
		SLNode nd = (SLNode) loc;
		if (nd.skipList !=this) throw new RuntimeException("Locator not of this List");
		removeTower(nd);
		size--;
		// can we reduce the height?
		if (height>2 && topLeft.below.after==topRight.below){
			topLeft.below=topLeft.below.below;
			topLeft.below.above=topLeft;
			topRight.below=topRight.below.below;
			topRight.below.above=topRight;
			height--;
		}
	}
	
	
	protected void removeTower(SLNode n){
		// find bottom (to be sure)
		while (n.below != null) n=n.below;
		while (n!=null){
			n.before.after=n.after;
			n.after.before=n.before;
			n.skipList = null; 
			n=n.above;
			nodeCnt--;
		}
	}



	public Iterator locators() {
		return new Iterator(){
			SLNode nd = SkipList.this.bottomLeft;
			public boolean hasNext() {
				return (nd.after != bottomRight);  
			}

			public Object next() {
				if (hasNext()){
					nd=nd.after;
					return nd;
				}
				else throw new RuntimeException("Iterator has no next element");
			}

			public void remove() {
				throw new RuntimeException("not implemented!");
			}};
		// TODO Auto-generated method stub
	}

	
	public Iterator findAll(Comparable key) {
		final SLNode nds = (SLNode)findClosestBefore(key);
		final Comparable k = key;
		return new Iterator(){
			SLNode nd = nds.after;
			public boolean hasNext() {
				return (nd.before.key.compareTo(k) == 0);  
			}

			public Object next() {
				if (hasNext()){
					nd=nd.before;
					return nd;
				}
				else throw new RuntimeException("Iterator has no next element");
			}

			public void remove() {
				throw new RuntimeException("not implemented!");
			}};
	}
	
	public int size() {
		Iterator<?> it = this.locators();
		int counter = 0;
		while(it.hasNext()){
			it.next();
			counter++;
		}
		return counter;
	}

	public void printAll(){
		SLNode nd=bottomLeft.after;
		for (int i = 0;i<size;i++){
			System.out.println(i+":: "+nd.key);
			nd=nd.after;
		}
	}

	public void printAllLevels(){
		SLNode nb = bottomLeft;
		for (int i=0;i<size;i++){
			nb=nb.after;
			SLNode nt = nb;
			for (int k=0;k<height-1;k++){
				if (nt!=null){
					System.out.print(String.format("%3d",nt.key)+" ");
					nt=nt.above;
				}
				else System.out.print(" |  "); 
			}
			System.out.println();
		}
	}

	public static void main(String[] args) {
		ThreadMXBean threadBean = ManagementFactory.getThreadMXBean();		
		java.util.Random rand=new java.util.Random(12256);
		int n=1000;
		Integer [] a = new Integer[n];
		SkipList sl = new SkipList(new Integer(-1),
				new Integer(Integer.MAX_VALUE),0.5);
		sl.debug=false;		
        
		
		for (int i=0;i<a.length;i++) a[i]=new Integer(rand.nextInt(1000));
		//sl.insertItem(new Integer(100),null);
		long before = threadBean.getCurrentThreadCpuTime();
		for (int i=0;i<a.length;i++) sl.insertItem(a[i],null);
		long after = threadBean.getCurrentThreadCpuTime();
		System.out.println("height:" + sl.height+" ,time: "+(after-before)/1000000+" msec");
		System.out.println("Height: "+sl.getHeight());
		for (int i=0;i<a.length/2;i++){
			System.out.println("remove");
			sl.removeItem(sl.findItem(a[i]));
		}
		System.out.println("*********");
//
		sl.printAllLevels(); 
//		System.out.println("*********");
//		sl.insertItem(new Integer(274), null);
//		sl.printAllLevels();
//		Locator loc = sl.findClosestAfter(new Integer(927));
//		System.out.println(loc.key());
//		System.out.println(sl.next(loc).key());

//		Iterator it = sl.findAll(new Integer(1005));
//		while(it.hasNext()){
//			Locator loc = (Locator) it.next();
//			System.out.println(loc.key());
//		}
//		System.out.println("*********");
// 		sl.printAll();
	}

}
